🤪 小镇刷题家 && 漫无止境之路 😭
剑指offer
所谓，少壮不努力，老大徒伤悲。大一大二不学算法，大三大四徒伤悲。
现在开始还来得及么？我不知道，不过呢，我曾听闻，
种一棵树最好的时机是十年前，然后是现在。
其实我没有什么感触呢。；）
TODO LIST：
- [ ]
JZ3 数组中重复的数字
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
数据范围：0≤n≤10000 进阶：时间复杂度O(n) ，空间复杂度O(n)
输入：[2,3,1,0,2,5,3] 返回值：2 说明：2或3都是对的
public static int duplicate (int[] numbers) {
HashSet<Integer> hashSet = new HashSet<>();
for (int i:numbers) {
if (!hashSet.add(i))
return i;
} return -1;
}
JZ4 二维数组中的查找
在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
[[ 1, 2, 8, 9],
[ 2, 4, 9,12],
[ 4, 7,10,13],
[ 6, 8,11,15]]
给定 target = 7，返回 true。给定 target = 3，返回 false。
// 逐行二分查找
public boolean binarySearch(int target, int[] array) {
int l = 0, r = array.length-1;
int mid;
while (l <= r) {
mid = (l + r) / 2;
if (array[mid] == target) return true;
else if (array[mid] < target) l = mid+1;
else r = mid-1; // array[mid] > target
}
return false;
}
public boolean Find(int target, int[][] array) {
// write code here
if (array[0].length == 0 || array[0][0] > target) return false;
for (int[] a:array){
if (binarySearch(target,a)) return true;
}
return false;
}
// 从左下角开始,利用数组特性
// current < target 向右查找
// current > target 向左查找
JZ5 替换空格
请实现一个函数，将一个字符串s中的每个空格替换成“%20”。
例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
数据范围:0≤len(s)≤1000。
保证字符串中的字符为大写英文字母、小写英文字母和空格中的一种。
public static String replaceSpace (String s) {
return s.replace(" ","%20");
}
输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
如输入{1,2,3}的链表如下图:
//public static ArrayList<Integer> arrayList = new ArrayList<>();
public static void ff(ListNode node) {
if (node != null) {
ff(node.next);
arrayList.add(node.val);
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ff(listNode);
return arrayList;
}
JZ6 从尾到头打印链表
public static ArrayList<Integer> arrayList = new ArrayList<>();
public static void ff(ListNode node) {
if (node != null) {
ff(node.next);
arrayList.add(node.val);
}
}
public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
ff(listNode);
return arrayList;
}
JZ7 重建二叉树
给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。
例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。
public TreeNode reConstructBinaryTree(int [] pre, int [] vin) {
int n = pre.length;
int m = vin.length;
//每个遍历都不能为0
if (n == 0 || m == 0)
return null;
//构建根节点
TreeNode root = new TreeNode(pre[0]);
for (int i = 0; i < vin.length; i++) {
//找到中序遍历中的前序第一个元素
if (pre[0] == vin[i]) {
//构建左子树
root.left = reConstructBinaryTree(
Arrays.copyOfRange(pre,1,i+1),
Arrays.copyOfRange(vin,0,i));
//构建右子树
root.right = reConstructBinaryTree(
Arrays.copyOfRange(pre,i+1,pre.length),
Arrays.copyOfRange(vin,i+1,vin.length));
break;
}
} return root;
}
JZ8 二叉树的下一个结点
给定一个二叉树其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的next指针。
// 获取根节点，记录中序遍历结果，遍历比对，返回下一节点
private ArrayList<TreeLinkNode> list = new ArrayList<>();
public TreeLinkNode GetNext(TreeLinkNode pNode) {
TreeLinkNode node = pNode;
while (node.next!=null) node=node.next;
f(node);
for (int i=0;i<list.size()-1;i++)
if (list.get(i)==pNode)
return list.get(i+1);
return null;
}
public void f(TreeLinkNode node) {
if (node==null) return;
f(node.left);
list.add(node);
f(node.right);
}
JZ9 用两个栈实现队列
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();
public void push(int node) {
stack1.push(node);
}
public int pop() {
if (stack2.isEmpty()){
while (!stack1.isEmpty()){
stack2.push(stack1.pop());
}
}
return stack2.pop();
}
JZ10 斐波那契数列
public int Fibonacci(int n) {
int i = 1, j = 1, k;
while (--n != 0) {
k = j;
j = i + j;
i = k;
}
return i;
}
Reference： 题解 #斐波那契数列#
JZ11 旋转数组的最小数字
// 二分法
public int minNumberInRotateArray(int[] nums) {
int i = 0, j = nums.length - 1, k;
while (i < j) {
k = i + (j - i) / 2;
// 旋转点在左排序数组
if (nums[k] < nums[j])
j = k;
// 旋转点在右排序数组
else if (nums[k] > nums[j])
i = k + 1;
else // nums[k]==nums[j]
j -= 1;
}
return nums[i];
}
JZ12 矩阵中的路径
请设计一个函数，用来判断在一个n乘m的矩阵中是否存在一条包含某长度为len的字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则该路径不能再进入该格子。
public char[][] natrix;
public boolean dfs(int i, int j, boolean[][] visited, String word) {
if (i > natrix.length - 1 || i < 0 || j < 0 || j > natrix[0].length - 1 ||
visited[i][j] || natrix[i][j] != word.charAt(0)) return false;
visited[i][j] = true;
if (word.length() == 1) return true;
word = word.substring(1);
boolean res = dfs(i + 1, j, visited, word)
||dfs(i - 1, j, visited, word)
||dfs(i, j + 1, visited, word)
||dfs(i, j - 1, visited, word);
visited[i][j] = false;
return res;
}
public boolean hasPath(char[][] matrix, String word) {
natrix = matrix;
boolean[][] visited = new boolean[20][20];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (dfs(i, j, visited, word))
return true;
}
} return false;
}
JZ14 剪绳子
给你一根长度为 n 的绳子，请把绳子剪成整数长的 m 段（ m 、 n 都是整数， n > 1 并且 m > 1 ， m <= n ），每段绳子的长度记为 k[1],...,k[m] 。请问 k[1]k[2]...*k[m] 可能的最大乘积是多少？
public int cutRope(int n) {
if (n <= 3)
return n - 1;
int res = 1;
while (n > 4) {
res *= 3;
n -= 3;
} return res * n;
}
Reference：
【1】证明，大数字都可以被拆分为多个2与3的和，以获取最大的乘积。
JZ16 数值的整数次方
实现函数 double Power(double base, int exponent)，求base的exponent次方。
注意：
1.保证base和exponent不同时为0。
2.不得使用库函数，同时不需要考虑大数问题
3.有特殊判题，不用考虑小数点后面0的位数。
// 直接计算
public double Power(double base, int exponent) {
double rs = 1;
if (exponent < 0) {
exponent = -exponent;
base = 1 / base;
}
while (exponent-- != 0) {
rs *= base;
} return rs;
}
// 快速幂
public double Power(double base, int exponent) {
double rs = 1;
if (exponent < 0) {
exponent = -exponent;
base = 1 / base;
}
while (exponent != 0) {
if ((exponent & 1) == 1)
rs *= base;
base *= base;
exponent >>= 1;
} return rs;
}
JZ18 删除链表的节点
public ListNode deleteNode(ListNode head, int val) {
ListNode node = head;
// 链表长度<=1
if (head.next == null) return null;
// val在头节点
if (head.val == val) return head.next;
while (node.next != null) {
// val在中间节点
if (node.next.val==val) {
node.next=node.next.next;
return head;
}
node = node.next;
} return null;
}
JZ21 调整数组顺序使奇数位于偶数前面(一)
输入一个长度为 n 整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
public int[] reOrderArray (int[] array) {
int n = array.length;
int[] res = new int[n];
int odd = 0;
for(int i = 0; i < n; i++){
if(array[i] % 2 == 1)
odd++;
}
int x = 0, y = odd;
for(int i = 0; i < n; i++){
if(array[i] % 2 == 1){
res[x] = array[i];
x++;
}else{
res[y] = array[i];
y++;
}
} return res;
}
JZ22 链表中倒数最后k个结点
// 无脑方法
public ListNode FindKthToTail(ListNode pHead, int k) {
if (pHead == null) return pHead;
ArrayList<ListNode> listNodes = new ArrayList<>();
while (pHead.next != null) {
listNodes.add(pHead);
pHead = pHead.next;
}
int index = listNodes.size() - k + 1;
if (index<0||k==0)return null;
return listNodes.get(listNodes.size() - k + 1);
}
// 双指针大法
public ListNode FindKthToTail(ListNode pHead, int k) {
ListNode p1 = pHead;
ListNode p2 = pHead;
while (k-- > 0) {
if (p1 != null) p1 = p1.next;
// k值过大
else return p1;
}
while (p1!=null){
p1=p1.next;
p2=p2.next;
}
return p2;
}
JZ23 链表中环的入口结点
给一个长度为n链表，若其包含环，请找出该链表的环的入口结点，否则，返回null。
// HashSet
public ListNode EntryNodeOfLoop(ListNode pHead) {
HashSet<ListNode> list = new HashSet<>();
while (pHead != null) {
if (!list.add(pHead))
return pHead;
pHead= pHead.next;
} return null;
}
// 双指针 快慢指针
JZ24 反转链表
public ListNode ReverseList(ListNode head) {
// write code here
if (head == null) return null;
ListNode pre = null, cur = head, next = head.next;
while (cur!=null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
JZ25 合并两个排序的链表
// 双指针比较头节点
public ListNode Merge(ListNode pHead1, ListNode pHead2) {
ListNode head = new ListNode(0);
ListNode temo = head;
if (pHead1 == null) return pHead2;
if (pHead2 == null) return pHead1;
while (pHead1 != null && pHead2 != null) {
if (pHead1.val <= pHead2.val) {
temo.next = pHead1;
pHead1 = pHead1.next;
} else {
temo.next = pHead2;
pHead2 = pHead2.next;
}
temo = temo.next;
}
if (pHead1 != null)
temo.next = pHead1;
else
temo.next = pHead2;
return head.next;
}
JZ26 树的子结构
public boolean f(TreeNode root1,TreeNode root2){
if (root2==null) return true;
if (root1==null) return false;
if (root1.val==root2.val)
return f(root1.left,root2.left) &&
f(root1.right, root2.right);
return false;
}
public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1==null||root2==null) return false;
ArrayDeque<TreeNode> nodes = new ArrayDeque<>();
nodes.offer(root1);
while (!nodes.isEmpty()){
TreeNode poll = nodes.poll();
if (poll.left!=null) nodes.offer(poll.left);
if (poll.right!=null) nodes.offer(poll.right);
if (poll.val==root2.val)
if (f(poll, root2))
return true;
} return false;
}
JZ27 二叉树的镜像
// 递归
public TreeNode Mirror (TreeNode pRoot) {
if (pRoot == null) return pRoot;
TreeNode left = Mirror(pRoot.left);
TreeNode right = Mirror(pRoot.right);
pRoot.left = right;
pRoot.right = left;
return pRoot;
}
JZ28 对称的二叉树
// 递归对比
boolean recursion(TreeNode left, TreeNode right) {
// 两个都为空
if (left == null && right == null)
return true;
// 只有一个为空或者节点值不同
if (left == null || right == null || left.val != right.val)
return false;
// 递归比较
return recursion(left.left, right.right) && recursion(left.right, right.left);
}
boolean isSymmetrical(TreeNode pRoot) {
return recursion(pRoot, pRoot);
}
JZ29 顺时针打印矩阵
// 边界模拟
public ArrayList<Integer> printMatrix(int [][] matrix) {
int up=0,down=matrix.length-1,left=0,right=matrix[0].length-1;
ArrayList<Integer> temo = new ArrayList<Integer>();
while(true){
int i;
// left -> right
for(i=left;i<=right;i++)
temo.add(matrix[up][i]);
if(++up>down)break;
// up -> down
for(i=up;i<=down;i++)
temo.add(matrix[i][right]);
if(--right<left)break;
// right -> left
for(i=right;i>=left;i--)
temo.add(matrix[down][i]);
if(--down<up)break;
// down -> up
for(i=down;i>=up;i--)
temo.add(matrix[i][left]);
if(++left>right)break;
}
return temo;
}
JZ31 栈的压入、弹出序列
public boolean IsPopOrder(int[] pushV, int[] popV) {
Stack<Integer> stack = new Stack<>();
int j=0;
for (int i : pushV) {
stack.push(i);
while (!stack.isEmpty()&&stack.peek()==popV[j]){
stack.pop();
if (++j==popV.length) return true;
}
} return false;
}
JZ32 从上往下打印二叉树
// queue 二叉树层序遍历
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
ArrayDeque<TreeNode> deque = new ArrayDeque<>();
if (root == null) return res;
deque.offer(root);
while (!deque.isEmpty()) {
TreeNode poll = deque.poll();
if (poll.left != null) deque.offer(poll.left);
if (poll.right != null) deque.offer(poll.right);
res.add(poll.val);
}
return res;
}
JZ33 二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回 true ,否则返回 false 。假设输入的数组的任意两个数字都互不相同。
// 单调栈法
public boolean VerifySquenceOfBST(int [] sequence) {
if(sequence.length==0) return false;
int root = Integer.MAX_VALUE;
Stack<Integer> stack = new Stack<Integer>();
for(int i=sequence.length-1;i>-1;i--){
if(sequence[i]>root) return false;
while(!stack.isEmpty()&&stack.peek()>sequence[i])
root=stack.pop();
stack.add(sequence[i]);
} return true;
}
JZ34 二叉树中和为某一值的路径(二)
输入一颗二叉树的根节点 root 和一个整数 target ，找出二叉树中结点值的和为 target 的所有路径。
public ArrayList<Integer> list = new ArrayList<>();
public ArrayList<ArrayList<Integer>> rs = new ArrayList<>();
public void f(TreeNode root, int t) {
if (root == null) return ;
list.add(root.val);
if (root.left == null && root.right == null && t == root.val)
rs.add(new ArrayList<>(list));
t -= root.val;
f(root.left, t);
f(root.right, t);
list.remove(list.size()-1);
}
public ArrayList<ArrayList<Integer>> FindPath (TreeNode root, int target) {
f(root, target);
return rs;
}
JZ36 二叉搜索树与双向链表
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示
// 递归中序遍历
public TreeNode pre=null;
public TreeNode head=null;
public void f(TreeNode node) {
if(node==null) return;
f(node.left);
if(pre==null){
pre=node;
head=node;
} else {
pre.right=node;
node.left=pre;
pre=node;
}
f(node.right);
}
public TreeNode Convert(TreeNode pRootOfTree) {
f(pRootOfTree);
return head;
}
// 非递归中序遍历 栈实现
JZ39 出现次数超过一半的数字
public int MoreThanHalfNum_Solution(int[] numbers) {
Arrays.sort(numbers);
return numbers[numbers.length/2];
}
// 投票算法
JZ42 连续子数组的最大和
// 动态规划
// 以array[i]为结尾的「最大子数组和」为dp[i]
// 并舍弃前面的以array[j]为结尾的和为负的子列
public int FindGreatestSumOfSubArray (int[] array) {
int n = array.length;
int maxSum = array[0];
int currSum = array[0];
for (int i = 1; i < n; i++) {
currSum = Math.max(array[i], currSum + array[i]);
maxSum = Math.max(maxSum, currSum);
}
return maxSum;
}
JZ47 礼物的最大价值
在一个 m×n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
// 动态规划 (可以直接修改元素组)
public int maxValue(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
dp[0][0] = grid[0][0];
// 初始化第一行和第一列
for (int i = 1; i < m; i++)
dp[i][0] = dp[i - 1][0] + grid[i][0];
for (int j = 1; j < n; j++)
dp[0][j] = dp[0][j - 1] + grid[0][j];
// 计算其余格子的最大礼物价值
for (int i = 1; i < m; i++)
for (int j = 1; j < n; j++)
dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) + grid[i][j];
return dp[m - 1][n - 1];
}
// 递归
JZ50 第一个只出现一次的字符
// HashMap
public int FirstNotRepeatingChar(String str) {
Map<Character, Integer> map = new HashMap<>();
for (char c : str.toCharArray())
map.put(c, map.getOrDefault(c,0) + 1);
for (char c : str.toCharArray())
if (map.get(c) == 1)
return str.indexOf(c);
return -1;
}
// queue
JZ52 两个链表的第一个公共结点
// 双指针遍历
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
ListNode n1=pHead1,n2=pHead2;
while (n1!=n2){
n1=n1==null?pHead2:n1.next;
n2=n2==null?pHead1:n2.next;
} return n1;
}
Reference：解题思路
JZ53 数字在升序数组中出现的次数
// 二分法 查找左右边界
private int binarySearch(int[] data, double k){
int left = 0,right = data.length - 1,mid;
while(left <= right){
mid = right+(left-right) / 2;
if(data[mid] < k)
left = mid + 1;
else if(data[mid] > k)
right = mid - 1;
}
return left;
}
public int GetNumberOfK(int [] array , int k) {
return binarySearch(array, k + 0.5) - binarySearch(array, k - 0.5);
}
JZ55 二叉树的深度
// 递归
public int TreeDepth(TreeNode root) {
if (root == null) return 0;
return Math.max(TreeDepth(root.left),TreeDepth(root.right))+1;
}
// queue 层序遍历
JZ56 数组中只出现一次的两个数字
一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。
数据范围：数组长度 2≤n≤1000，数组中每个数的大小 0<v≤1000000
// HashSet (初始想法)
public int[] FindNumsAppearOnce(int[] nums) {
HashSet<Integer> set = new HashSet<>();
for (int i : nums)
if (!set.add(i)) set.remove(i);
Iterator<Integer> iterator = set.iterator();
Integer a = iterator.next();
Integer b = iterator.next();
return a<b?new int[]{a,b}:new int[]{b,a};
}
// 异或运算 (推荐)
public int[] FindNumsAppearOnce(int[] nums) {
// 计算数组中所有数字的异或结果
int xorResult = 0;
for (int num : nums)
xorResult ^= num;
// 找到异或结果中最低位的1
int mask = 1;
while ((xorResult & mask) == 0)
mask <<= 1;
// 将数组分成两组，一组包含指定位为1的数字，另一组包含指定位为0的数字
int num1 = 0;
int num2 = 0;
for (int num : nums) {
if ((num & mask) == 0)
num1 ^= num;
else
num2 ^= num;
}
return num1<num2?new int[]{num1, num2}:new int[]{num2, num1};
}
Reference： 题解 | #数组中只出现一次的两个数字#
JZ57 和为S的两个数字
输入一个升序数组 array 和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，返回任意一组即可，如果无法找出这样的数字，返回一个空数组即可。
// 双指针遍历
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
int i=0,j=array.length-1,rs;
ArrayList<Integer> arrayList = new ArrayList<>();
while (i<j){
rs = array[i] + array[j];
if (rs==sum){
arrayList.add(array[i]);
arrayList.add(array[j]);
break;
}
else if (rs>sum) j--;
else i++;
} return arrayList;
}
// HashMap (不推荐)
JZ61 扑克牌顺子
public boolean IsContinuous (int[] numbers) {
HashSet<Integer> cards = new HashSet<>();
for (int i:numbers) {
if (i == 0) continue;
if (!cards.add(i)) return false;
}
Iterator<Integer> iterator = cards.iterator();
int max = 0;
int min = iterator.next();
while (iterator.hasNext()) max = iterator.next();
return max-min<5;
}
JZ63 买卖股票的最好时机(一)
public int maxProfit(int[] prices) {
if (prices == null) return 0;
int maxProfit=0,minPoint=Integer.MAX_VALUE;
for (int price : prices) {
minPoint = Math.min(minPoint, price);
maxProfit = Math.max(maxProfit, price - minPoint);
}
return maxProfit;
}
JZ65 不用加减乘除做加法
// A+B = A^B + (A&B) << 1
public int Add(int a, int b) {
// 当进位为0时，表示没有需要进位的位，此时计算结束
while (b != 0) {
// 计算进位，使用异或运算
int carry = a & b;
// 计算无进位的和，使用异或运算
a = a ^ b;
// 将进位左移一位，作为下一次运算的进位
b = carry << 1;
} return a;
}
JZ66 构建乘积数组
给定一个数组 A[0,1,...,n-1] ,请构建一个数组 B[0,1,...,n-1] ,其中 B 的元素 B[i]=A[0]A[1]...*A[i-1]A[i+1]...*A[n-1]（除 A[i] 以外的全部元素的的乘积）。程序中不能使用除法。（注意：规定 B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2]）
对于 A 长度为 1 的情况，B 无意义，故而无法构建，用例中不包括这种情况。
JZ68 二叉搜索树的最近公共祖先
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.
2.二叉搜索树是，若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值； 若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值
3.所有节点的值都是唯一的。
4.p、q 为不同节点且均存在于给定的二叉搜索树中。
public int lowestCommonAncestor (TreeNode root, int p, int q) {
if (root==null) return -1;
if (root.val>=q&&root.val<=p||root.val<=q&&root.val>=p) return root.val;
if (p>= root.val) return lowestCommonAncestor(root.right,p,q);
return lowestCommonAncestor(root.left,p,q);
}
JZ69 跳台阶
public int jumpFloor (int number) {
if(number==1||number==0) return 1;
return jumpFloor(number-1)+jumpFloor(number-2);
}
JZ71 跳台阶扩展问题
public int jumpFloorII (int number) {
if(number==1||number==0)return 1;
return 2*jumpFloorII(number-1);
}
JZ73 翻转单词序列
public String ReverseSentence(String str) {
String[] s = str.split(" ");
StringBuilder ss = new StringBuilder();
for (int i=s.length-1;i>-1;i--){
ss.append(s[i]).append(" ");
} return ss.toString().trim();
}
JZ79 判断是不是平衡二叉树
输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
public int depth(TreeNode node) {
if (node == null) return 0;
int left = depth(node.left);
if (left == -1) return -1;
int right = depth(node.right);
if (right == -1) return -1;
if (Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
}
public boolean IsBalanced_Solution(TreeNode pRoot) {
return depth(pRoot)!=-1;
}
JZ81 调整数组顺序使奇数位于偶数前面(二)
输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，对奇数和奇数，偶数和偶数之间的相对位置不做要求
// 双指针
public int[] reOrderArrayTwo (int[] array) {
int i = 0;
int j = array.length - 1;
while(i < j){
if(array[i] % 2 == 1 && array[j] % 2 == 1)
i++;
else if(array[i] % 2 == 1 && array[j] % 2 == 0){
i++;
j--;
}
else if(array[i] % 2 == 0 && array[j] % 2 == 1){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
else
j--;
}
return array;
}
// ArrayDeque: offerFirst() offerLast()
public int[] reOrderArrayTwo(int[] array) {
ArrayDeque<Integer> arrayList = new ArrayDeque<>();
for (int i : array) {
if (i % 2 == 0) {
arrayList.offerLast(i);
} else {
arrayList.offerFirst(i);
}
}
int[] res = new int[arrayList.size()];
int index = 0;
for (int i: arrayList)
res[index++]=i;
return res;
}
JZ82 二叉树中和为某一值的路径(一)
给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
// 递归
public boolean hasPathSum (TreeNode root, int sum) {
if (root==null) return false;
if (sum-root.val==0&&root.left==null&&root.right==null) return true;
return hasPathSum(root.left,sum-root.val)||hasPathSum(root.right,sum-root.val);
}
// 非递归 dfs Stack
BM 牛客题霸-模板速刷 TOP101
BM53 缺失的第一个正整数
给定一个无重复元素的整数数组 nums，请你找出其中没有出现的最小的正整数
数据范围： −231≤*nums*[*i*]≤231−1, 0≤len(nums)≤5∗10^5
public int minNumberDisappeared(int[] nums) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i : nums)
map.put(i, 1);
int rs = 1;
while(map.containsKey(rs))
rs++;
return rs;
}
BM78 打家劫舍(一)
public int rob (int[] nums) {
if(nums.length==1)return nums[0];
int[] dp = new int[nums.length];
dp[0]=nums[0];
dp[1]=Math.max(dp[0],nums[1]);
for (int i=2;i<nums.length;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
} return dp[nums.length-1];
}
BM79 打家劫舍(二)
你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。
给定一个长度为 n 的整数数组 nums ，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。
public int rob (int[] nums) {
if(nums.length==1)return nums[0];
int[] dp = new int[nums.length];
dp[0]=nums[0];
dp[1]=Math.max(dp[0],nums[1]);
for (int i=2;i<nums.length;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
} int max = dp[nums.length-2];
dp[0]=0;
dp[1]=nums[1];
for (int i=2;i<nums.length;i++){
dp[i]=Math.max(dp[i-1],dp[i-2]+nums[i]);
} return Math.max(max,dp[nums.length-1]);
}
BM80 买卖股票的最好时机(一)
假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天
2.如果不能获取到任何利润，请返回0
3.假设买入卖出均无手续费
// 贪心
public int maxProfit(int[] prices) {
if (prices == null) return 0;
int maxProfit=0,minPoint=Integer.MAX_VALUE;
for (int price : prices) {
minPoint = Math.min(mi nPoint, price);
maxProfit = Math.max(maxProfit, price - minPoint);
} return maxProfit;
}
// 动态规划
public int maxProfit (int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
} return dp[prices.length-1][0];
}
BM81 买卖股票的最好时机(二)
假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
- 你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
- 如果不能获取收益，请返回0
- 假设买入卖出均无手续费
// 动态规划
public int maxProfit (int[] prices) {
int[][] dp = new int[prices.length][2];
dp[0][0] = 0;
dp[0][1] = -prices[0];
for(int i = 1; i < prices.length; i++){
dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);
dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);
} return dp[prices.length-1][0];
}
